/**
 * @file   zhtable.h
 * @author karpar Hu <huzhili@gmail.com>
 * @date   Thu May  7 10:09:36 2009
 * 
 * @brief  A hash table class for easy use.
 *         This is a dense table, which is a particular implementation of
 *         a hashtable: one that using an array to store all the data.
 */

/**
 * To minimize allocation and pointer overhead, we use insternal
 * probing, in which the hash table is a single table, and collisions
 * are resolved by trying to insert again in another bucket. The most
 * cache-efficient internal probing schemes are linear probing and quardratic
 * probing.
 *
 * Let h(k) be a hash function that maps an element k to an integer 
 * in [0,m . 1], where m is the size of the table.
 * Let the ith probe position for a value k be given by the function
 * h(k,i) = (h(k) + c1i + c2i^2)(mod m), where . If c2 = 0, then h(k,i)
 * degrades to a linear probe. For a given hash table, the values of 
 * c1 and c2 remain constant.
 * 
 * Example: 
 * If h(k,i) = (h(k) + i + i^2)(mod m), then the probe sequence will be h(k),
 * h(k) + 2,h(k) + 6,...
 * For m = 2n, a good choice for the constants are c1 = c2 = 1/2, as the 
 * values h(k,i) for i in [0,m . 1] are all distinct. [1] This leads to a
 * probe sequence of h(k),h(k) + 1,h(k) + 3,h(k) + 6,... where the values
 * increase by 1,2,3,....
 * For prime m > 2, most choices of c1 and c2 will make h(k,i) distinct 
 * for i in [0,(m . 1) / 2]. Such choices include c1 = c2 = 1/2, c1 = c2 = 1,
 * and c1 = 0,c2 = 1. Because there are only about m/2 distinct probes 
 * for a given element, it is difficult to guarantee that insertions will
 * succeed when the load factor is > 1/2.
 * HT_OCCUPANCY_FLT -- how full before we duoble size.
 * HT_EMPTY_FLT -- how empty before we halve size
 * HT_MIN_BUCKETS -- default smallest bucket size.
 * Default shrink resize is .4 * OCCUPANCY_FLT
 *
 */

// #ifndef _ZHTABLE_H_
// #define _ZHTABLE_H_

// /* The probing method
//  * Linear probing
//  * #define JUMP_(key, num_probes) (1)
//  * Quadratic-is probing
//  */
// #define JUMP_(key, num_probes) (num_probes)

// #include <assert.h>
// #include <stdio.h>
// #include <stdlib.h>             /* abort() */
// #include <algorithm>            /* swap() */
// #include <iostream>             /* cerr() */
// #include <memory>               /* For uninitialized_fill, uninitialize_copy */
// #include <utility>              /* for pair<> */
// #include <iterator>              /* for facts about iterator tags */

// using std::pair;



// template<class T, T v>
// struct integral_constant {
//   static const T value = v;
//   typedef T value_type;
//   typedef integral_constant<T, v> type;
// };

// template <class T, T v> const T integral_constant<T, v>::value;

// // Abbreviations: true_type and false_type are structs that represent
// // boolean true and false values.
// typedef integral_constant<bool, true>  true_type;
// typedef integral_constant<bool, false> false_type;

// template <class V, class K, class HashFn,
//           class ExtractKey, class EqualKey, class Alloc>
// class hashtable;

// template <class V, class K, class HF, class ExK, class EqK, class A>
// struct hash_table_iterator;

// template <class V, class K, class HF, class ExK, class EqK, class A>
// struct hash_table_const_iterator;


// template <class V, class K, class HF, class ExK, class EqK, class A>
// struct hash_table_iterator {
// public:
//   typedef hash_table_iterator<V, K, HF, ExK, EqK, A> iterator;
//   typedef hash_table_const_iterator<V, K, HF, ExK, EqK, A> const_iterator;

//   typedef std::forward_iterator_tag iterator_category;
//   typedef V value_type;
//   typedef ptrdiff_t difference_type;
//   typedef V& reference;         // Value.
//   typedef V* pointer;

//   // constructor and default constructor
//   hash_table_iterator(const hashtable<V,K,HF,ExK,EqK,A> *h,
//                       pointer it, pointer it_end, bool advance)
//     : ht(h), pos(it), end(it_end) {
//     if (advance) advance_past_empty_and_deleted();
//   }
//   hash_table_iterator() {}

//   // make sure that we're not on an empty or marked-deleted array element.
//   void advance_past_empty_and_deleted() {
//     while (pos != end && (ht->test_empty(*this) || ht->test_deleted(*this)))
//       ++pos;
//   }

//   reference operator*() { return *pos; }
//   pointer operator->() { return &(operator*()); }

//   // Comparison
//   bool operator==(const iterator& it) const { return pos == it.pos; }
//   bool operator!=(const iterator& it) const { return pos != it.pos; }

//   iterator& operator++() {
//     assert(pos != end); ++pos; 
//     advance_past_empty_and_deleted(); 
//     return pos;
//   }

//   iterator operator++(int) {
//     iterator tmp(*this); 
//     ++*this;
//     return tmp;
//   }
//   // The actual data
//   const hashtable<V,K,HF,ExK,EqK,A> *ht;
//   pointer pos, end;
// };

// template <class V, class K, class HF, class ExK, class EqK, class A>
// struct hash_table_const_iterator {
// public:
//   typedef hash_table_iterator<V, K, HF, ExK, EqK, A> iterator;
//   typedef hash_table_const_iterator<V, K, HF, ExK, EqK, A> const_iterator;

//   typedef std::forward_iterator_tag iterator_category;
//   typedef V value_type;
//   typedef ptrdiff_t difference_type;
//   typedef size_t size_type;
//   typedef const V& reference;   // value
//   typedef const V* pointer;

//   hash_table_const_iterator(const hashtable<V,K,HF,ExK,EqK,A> *h,
//                            pointer it, pointer it_end, bool advance)
//     : ht(h), pos(it), end(it_end) {
//     if (advance) advance_past_empty_and_deleted();
//   }

//   hash_table_const_iterator() { };
//   // let regular iterator to const iterator
//   hash_table_const_iterator(const iterator &it) 
//     : ht(it.ht), pos(it.pos), end(it.end) { }
  
//   reference operator*() { return *pos; }
//   pointer operator->() { return &(operator*()); }

//   void advance_past_empty_and_deleted() { 
//     while (pos != end && (ht->test_empty(*this) || ht->test_deleted(*this))) 
//       ++pos;
//   }

//   const_iterator& operator++() { 
//     assert(pos != end); ++pos; advance_past_empty_and_deleted(); 
//     return pos;
//   }

//   const_iterator operator++(int) {
//     const_iterator tmp(*this);
//     ++(*this);
//     return tmp;
//   }

//   bool operator==(const iterator& it) { return pos == it.pos; }
//   bool operator!=(const iterator& it) { return pos != it.pos; }

//   const hashtable<V,K,HF,ExK,EqK,A> *ht;
//   pointer pos, end;
// };

// template <class V, class K, class HashFn,
//           class ExtractKey, class EqualKey, class Alloc>
// class hashtable {
// public:
//   typedef K key_type;
//   typedef V value_type;
//   typedef HashFn hasher;
//   typedef EqualKey key_equal;

//   typedef size_t size_type;
//   typedef ptrdiff_t difference_type;
//   typedef value_type* pointer;
//   typedef const value_type* const_pointer;
//   typedef hash_table_iterator<V, K, HashFn, 
//                               ExtractKey, EqualKey, Alloc> iterator;

//   typedef hash_table_const_iterator<V, K, HashFn, ExtractKey, 
//                                     EqualKey, Alloc> const_iterator;

//   static const float HT_OCCUPANCY_FLT; // 0.8
//   static const float HT_EMPTY_FLT;     // 0.4
//   static const float HT_MIN_BUCKETS = 4;
  
//   static const size_t HT_DEFAULT_STARTING_BUCKETS = 32;

//   // ITERATOR FUNCTIONS
//   iterator begin() { return iterator(this, table,
//                                      table +num_buckets, true); }
//   iterator end() { return iterator(this, table + num_buckets,

//                                    table + num_buckets, true); }

//   const_iterator begin() const { return const_iterator(this, table,
//                                                  table + num_buckets, true); }
//   const_iterator end() const { return const_iterator(this, table+num_buckets, 
//                                                table+num_buckets, true); }

//   // ACCESSOR FUNCTIONS for the things we templatize on, basically
//   hasher hash_funct() const { return hash; }
//   key_equal key_eq() const { return equals; }

// private:
//   // We use explicit destructor invocation and placement new to get
//   // around this.
//   void set_value(value_type* dst, const value_type& src) {
//     dst->~value_type();
//     new(dst) value_type(src);
//   }

//   void destroy_buckets(size_type first, size_type last) {
//     for ( ; first != last; ++first)
//       table[first].~value_type();
//   }
//   // DELETE HELPER FUNCTIONS
// private:
//   void squash_deleted() {
//     if (num_deleted) {
//       hashtable tmp(*this);
//       swap(tmp);                // now in tmp
//     }
//     assert(num_deleted == 0);
//   }

// public:
//   void set_deleted_key(const value_type &val) {
//     assert(!use_empty || !equals(get_key(val), get_key(emptyval)));
//     squash_deleted();
//     use_deleted = true;
//     set_value(&delval, val);
//   }
//   void clear_deleted_key() {
//     squash_deleted();
//     use_deleted = false;
//   }

//   bool test_deleted(size_type bucknum) const {
//     return (use_deleted && num_deleted > 0 &&
//             equals(get_key(delval), get_key(table[bucknum])));
//   }

//   bool test_deleted(const iterator& it) const {
//     return (use_deleted && num_deleted > 0 &&
//             equals(get_key(delval), get_key(*it)));
//   }

//   bool test_deleted(const const_iterator& it) const {
//     return (use_deleted && num_deleted > 0 &&
//             equals(get_key(delval), get_key(*it)));
//   }

//   // set it so test_deleted is true.
//   bool set_deleted(const_iterator& it) {
//     assert(use_deleted);
//     bool retval = !test_deleted(it);
//     set_value(const_cast<value_type*>(&(*it)), delval);
//     return retval;
//   }

//   bool clear_deleted(const_iterator& it) {
//     assert(use_deleted);
//     return test_deleted(it);
//   }

// public:
//   bool test_empty(size_type bucknum) const {
//     assert(use_empty);
//     return equals(get_key(emptyval), get_key(table[bucknum]));
//   }

//   bool test_empty(const iterator& it) const {
//     assert(use_empty);
//     return equals(get_key(emptyval), get_key(*it));
//   }

//   bool test_empty(const const_iterator& it) const {
//     assert(use_empty);
//     return equals(get_key(emptyval), get_key(*it));
//   }

// private:
//   void set_empty(size_type bucknum) {
//     assert(use_empty);
//     set_value(&table[bucknum], emptyval);
//   }
//   void fill_range_with_empty(value_type* s, value_type* e) {
//     std::uninitialized_fill(s,e,emptyval);
//   }
//   void set_empty(size_type buckstart, size_type buckend) {
//     assert(use_empty);
//     destroy_buckets(buckstart, buckend);
//     fill_range_with_empty(table + buckstart, table + buckend);
//   }

// public:
//   void set_empty_key(const value_type& val) {
//     assert(!use_empty);
//     assert(!use_deleted || !equals(get_key(val), get_key(delval)));
//     use_empty = true;
//     set_value(&emptyval, val);

//     assert(!table);             // 
//     table = (value_type *)malloc(num_buckets * sizeof(*table));
//     assert(table);
//     fill_range_with_empty(table, table + num_buckets);
//   }

// public:
//   size_type size() const { return num_elements - num_deleted; }
//   size_type max_size() const { return (size_type(-1) >> 1U) + 1; }
//   bool emtpy() const { return size() == 0; }
//   size_type bucket_count() const { return num_buckets; }
//   size_type nonempty_bucket_count() const { return num_elements; }

// private:
//   // size_type(-1) is never legal; errors!
//   static const size_type ILLEGAL_BUCKET = size_type(-1);

// private:
//   size_type min_size(size_type num_elts, size_type min_buckets_wanted) {
//     size_type sz = HT_MIN_BUCKETS;
//     while (sz < min_buckets_wanted || num_elts >= sz * enlarge_resize_percent)
//       sz *= 2;
//     return sz;
//   }

//   void maybe_shrink() {
//     assert(num_elements >= num_deleted);
//     assert((bucket_count() & (bucket_count() - 1)) == 0);
//     assert(bucket_count() >= HT_MIN_BUCKETS);

//     if (shrink_threshold > 0 &&
//         (num_elements - num_deleted) < shrink_threshold &&
//         bucket_count() > HT_DEFAULT_STARTING_BUCKETS ) {
//       size_type sz = bucket_count() / 2;
//       while (sz > HT_DEFAULT_STARTING_BUCKETS &&
//              (num_elements - num_deleted) < sz * shrink_resize_percent)
//         sz /= 2;
//       hashtable tmp(*this, sz);
//       swap(tmp);                // now we are tmp
//     }
//     consider_shrink = false;
//   }

//   void resize_delta(size_type delta) {
//     if ( consider_shrink )   
//       maybe_shrink();
//     if ( bucket_count() > HT_MIN_BUCKETS &&
//          (num_elements + delta) <= enlarge_threshold )
//       return;     
    
//     const size_type needed_size = min_size(num_elements + delta, 0);
//     if ( needed_size > bucket_count() ) {      // we don't have enough buckets
//       const size_type resize_to = min_size(num_elements - num_deleted + delta,
//                                            0);
//       hashtable tmp(*this, resize_to);
//       swap(tmp);                             // now we are tmp
//     }
//   }

//   void expand_array(size_t resize_to, true_type) {
//     table = (value_type *) realloc(table, resize_to * sizeof(value_type));
//     assert(table);
//     fill_range_with_empty(table + num_buckets, table + resize_to);
//   }

//   void expand_array(size_t resize_to, false_type) {
//     value_type* new_table = (value_type *) realloc(table, resize_to * sizeof(value_type));
//     assert(new_table);
//     std::uninitialized_copy(table, table + num_buckets, new_table);
//     fill_range_with_empty(new_table, new_table + resize_to);
//     destroy_buckets(0, num_buckets);
//     free(table);
//     table = new_table;
//   }

//   // Used to actually do the rehashing when we grow/shrink a hashtable
//   void copy_from(const hashtable &ht, size_type min_buckets_wanted) {
//     clear();            // clear table, set num_deleted to 0

//     // If we need to change the size of our table, do it now
//     const size_type resize_to = min_size(ht.size(), min_buckets_wanted);
//     if ( resize_to > bucket_count() ) { // we don't have enough buckets
//       typedef integral_constant<bool,
//         (has_trivial_copy<value_type>::value &&
//          has_trivial_destructor<value_type>::value)>
//         realloc_ok; // we pretend mv(x,y) == "x.~T(); new(x) T(y)"
//       expand_array(resize_to, realloc_ok());
//       num_buckets = resize_to;
//       reset_thresholds();
//   }

//     // We use a normal iterator to get non-deleted bcks from ht
//     // We could use insert() here, but since we know there are
//     // no duplicates and no deleted items, we can be more efficient
//     assert((bucket_count() & (bucket_count()-1)) == 0);      // a power of two
//     for ( const_iterator it = ht.begin(); it != ht.end(); ++it ) {
//       size_type num_probes = 0;              // how many times we've probed
//       size_type bucknum;
//       const size_type bucket_count_minus_one = bucket_count() - 1;
//       for (bucknum = hash(get_key(*it)) & bucket_count_minus_one;
//            !test_empty(bucknum);                               // not empty
//            bucknum = (bucknum + JUMP_(key, num_probes)) & bucket_count_minus_one) {
//         ++num_probes;
//         assert(num_probes < bucket_count()); // or else the hashtable is full
//       }
//       set_value(&table[bucknum], *it);       // copies the value to here
//       num_elements++;
//     }
//   }

// public:
//   void resize(size_type req_elements) {
//     if (consider_shrink || req_elements == 0)
//       maybe_shrink();
//     if (req_elements > num_elements)
//       return resize_delta(req_elements - num_elements);
//   }

//   void set_resizing_parameters(float shrink, float grow) {
//     assert(shrink >= 0.0);
//     assert(grow <= 1.0);
//     assert(shrink <= grow / 2.0);
//     shrink_resize_percent = grow;
//     reset_thresholds();
//   }

//   // default constructor
//   explicit hashtable(size_type expected_max_items_in_table = 0,
//                      const HashFcn& hf = HashFcn(),
//                      const EqualKey& eql = EqualKey(),
//                      const ExtractKey& ext = ExtractKey())
//     : hash(hf), equals(eql), get_key(ext), num_deleted(0),
//       use_deleted(false), use_empty(false),
//       delvel(), emptyval(), enlarge_resize_percent(HT_OCCUPANCY_FLT),
//       shrink_resize_percent(HT_EMPTY_FLT), table(NULL),
//       num_buckets(expected_max_items_in_table == 0
//                   ? HT_DEFAULT_STARTING_BUCKETS
//                   : min_size(expected_max_items_in_table, 0)),
//       num_elements(0) {
//     reset_thresholds();
//   }

//   // copy-constructor
//   hashtable(const hashtable& ht,
//             size_type min_buckets_wanted = HT_DEFAULT_STARTING_BUCKETS)
//     : hash(ht.hash), equals(ht.equals), get_key(ht.get_key), num_deleted(0),
//       use_deleted(ht.use_deleted), use_empty(ht.use_empty),
//       delvel(ht.use_deleted), emptyval(ht.use_empty), 
//       enlarge_resize_percent(ht.enlarge_resize_percent),
//       shrink_resize_percent(ht.enlarge_resize_percent), table(NULL),
//       num_buckets(0), num_elements(0) {
//     reset_thresholds();
//     copy_from(ht, min_buckets_wanted);
//   }

//   // assigment
//   hashtable& operator= (const hashtable& ht) {
//     if (&ht == this) return *this;
//     clear();
//     hash = ht.hash;
//     equals = ht.equals;
//     get_key = ht.get_key;
//     use_deleted = ht.use_deleted;
//     use_empty = ht.use_empty;
//     set_value(&delval, ht.delval);
//     set_value(&emptyval, ht.emptyval);
//     enlarge_resize_percent = ht.enlarge_resize_percent;
//     shrink_resize_percent = ht.shrink_resize_percent;
//     copy_from(ht, HT_MIN_BUCKETS); // sets num_deleted to 0 too.
//     return *this;
//   }
//   ~hashtable() {
//     if (table) {
//       destroy_buckets(0, num_buckets);
//       free(table);
//     }
//   }

//   void swap(hashtable& ht) {
//     std::swap(hash, ht.hash);
//     std::swap(equals, ht.equals);
//     std::swap(get_key, ht.get_key);
//     std::swap(num_deleted, ht.num_deleted);
//     std::swap(use_deleted, ht.use_deleted);
//     std::swap(use_empty, ht.use_empty);
//     std::swap(enlarge_resize_percent, ht.enlarge_resize_percent);
//     std::swap(shrink_resize_percent, ht.shrink_resize_percent);
//     { value_type tmp;     // for annoying reasons, swap() doesn't work
//       set_value(&tmp, delval);
//       set_value(&delval, ht.delval);
//       set_value(&ht.delval, tmp);
//     }
//     { value_type tmp;     // for annoying reasons, swap() doesn't work
//       set_value(&tmp, emptyval);
//       set_value(&emptyval, ht.emptyval);
//       set_value(&ht.emptyval, tmp);
//     }
//     std::swap(table, ht.table);
//     std::swap(num_buckets, ht.num_buckets);
//     std::swap(num_elements, ht.num_elements);
//     reset_thresholds();
//     ht.reset_thresholds();
//   }

//   // It's always nice to be able to clear a table without deallocating it
//   void clear() {
//     if (table) 
//       destroy_buckets(0, num_buckets);
//     num_buckets = min_size(0, 0);
//     reset_thresholds();
//     table = (value_type *) realloc(table, num_buckets * sizeof(*table));
//     assert(table);
//     fill_range_with_empty(table, table + num_buckets);
//     num_elements = 0;
//     num_deleted = 0;
//   }

//   void clear_no_resize() {
//     if (table) {
//       set_empty(0, num_buckets);
//     }
//     reset_thresholds();
//     num_elements = 0; 
//     num_deleted = 0;
//   }


//   // Lookup routines
// private:
//   pair<size_type, size_type> find_position(const key_type &key) const {
//     size_type num_probes = 0;
//     const size_type  bucket_count_minus_one = bucket_count() - 1;
//     size_type bucknum = hash(key) & bucket_count_minus_one;
//     size_type insert_pos = ILLEGAL_BUCKET;
//     while ( 1 ) {
//       if ( test_empty(bucknum) ) {
//         if (insert_pos == ILLEGAL_BUCKET)
//           return pair<size_type, size_type>(ILLEGAL_BUCKET, bucknum);
//         else 
//           return pair<size_type, size_type>(ILLEGAL_BUCKET, insert_pos);
//       } else if ( test_deleted(bucknum) ) { // keep searching, but mark to.
//         if ( insert_pos == ILLEGAL_BUCKET)
//           insert_pos = bucknum;
//       } else if ( equals(key, get_key(table[bucknum]))) {
//         return pair<size_type, size_type>(bucknum, ILLEGAL_BUCKET);
//       }
//       ++num_buckets;
//       bucknum = (bucknum + JUMP_(key, num_probes)) & bucket_count_minus_one;
//       assert(num_probes<bucket_count());
//     }
//   }

// public:
//   iterator find(const key_type& key) {
//     if (size() == 0) return end();
//     pair<size_type, size_type> pos = find_position(key);
//     if (pos.first == ILLEGAL_BUCKET) // alas, not there
//       return end();
//     else
//       return iterator(this, table+pos.first, table+num_buckets, false);
//   }

//   const_iterator find(const key_type& key) {
//     if (size() == 0) return end();
//     pair<size_type, size_type> pos = find_position(key);
//     if (pos.first == ILLEGAL_BUCKET) // alas, not there
//       return end();
//     else
//       return const_iterator(this, table+pos.first, table+num_buckets, false);
//   }

//   size_type count(const key_type &key) const {
//     pair<size_type, size_type> pos = find_position(key);
//     return pos.first == ILLEGAL_BUCKET ? 0 : 1;
//   }

//   pair<iterator, iterator> equal_range(const key_type& key) {
//     const iterator pos = find(key); // either an iterator or end
//     return pair<iterator, iterator>(pos, pos);
//   }

//   pair<const_iterator, const_iterator> equal_range(const key_type& key) {
//     const const_iterator pos = find(key);
//     return pair<iterator, iterator>(pos, pos);
//   }

// private:

// private:

//   hasher hash;                  // required by hashd_associative_container
//   key_equal equals;
//   ExtractKey get_key;
//   size_type num_deleted;        // marked deleted
//   bool use_deleted;             // false until delval has been set
//   bool use_empty;               // you must do this before you start
//   value_type delval;            // which key marks deleted entries
//   value_type emptyval;          // which key marks unused entries

//   size_type num_buckets;
//   size_type num_elements;
//   size_type shrink_threshold;   // num_buckets * shrink_resize_percent
//   size_type enlarge_threshold;  // num_buckets * enlarge_resize_percent
//   value_type *table;

//   float enlarge_resize_percent;
//   float shrink_resize_percent;
//   bool consider_shrink;

// };

// #endif /* _ZHTABLE_H_ */
